package swordoffer.offer53_1;

/**
 * 该题与lc34为原题
 */
public class Search {
    /**
     *
     * 在排序数组中出现的次数，只需要找到数字第一次出现的位置 和 最后一次出现的位置
     *
     * 出现的次数 = last - first + 1;
     *
     */
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        //寻找target第一次出现的位置
        int first = findFirst(nums, target);
        //如果没找到，说明不存在该数字，直接返回0
        if(first == -1){
            return 0;
        }
        int last = findLast(nums, target);
        return last - first + 1;
    }
    public int findFirst(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }
    public int findLast(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid;
            }
        }
        return left;
    }
}
